package elementary_alg.array;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author : Kong Decheng
 * @date : 2021/04/02
 * @description: 只出现一次的数字
 */
public class LC5 {
    /**
     * 排序，找相邻不相等的元素
     *
     * @return
     */
    public int solution_1(int[] nums) {
        Arrays.sort(nums);
        int i = 0;
        // 如果元素是最后一个，说明非重复元素在数组末尾
        while (i + 1 != nums.length) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
            i += 2;
        }
        return nums[nums.length - 1];
    }

    /**
     * 位运算
     * 规律：
     * 1^1=0 1^0=1 0^1=1 0^0=0
     * 总结：
     * 1. a^a = 0 自己和自己异或结果为 0
     * 2. a^0 = a 任何数字和 0 异或结果等于它本身
     * 3. a^b^c=a^c^b 异或运算具有交换律
     *
     * @param nums
     * @return
     */
    public int solution_2(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }

    /**
     * 使用 set,将元素添加到集合中，如果添加失败，说明之前添加过该元素，则移除它
     * 最后，集合中只会剩下一个元素，就是我们要求解的值
     *
     * @param nums
     * @return
     */
    public int solution_3(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) {
                // 添加失败，则移除该元素
                set.remove(num);
            }
        }
        // 将集合转为数组获取值，并强转类型
        return (int) set.toArray()[0];
    }

}
